Most modern very large scale integration (VLSI) systems may be built according to the so-called “System-on-Chip” (SoC) concept. SoC functionalities are the result of the cooperation between several simple modules, which are generally selected by the designer from a preexisting library. The designer's role is to map the SoC functions onto that of the modules of the library. However, effective communication and interconnection systems may be helpful to meet desired performance for the designed SoC and, in particular, to provide effective communication between the nodes of the network.
As system complexity increases, on-Chip communication may become more critical. And current on-Chip communication systems may become complex infrastructures. In the next few years, SoC may include hundreds of communicating blocks running at many Gigahertz. Such systems are known as multiprocessor System-on-Chips (MP-SoCs). Researchers have recently provided the so-called Network-on Chip (NoC) concept to overcome the limitations relating to significant efforts used to adequately design on-Chip communication systems, even for the MP-SoCs systems.
NoC is an approach to provide scalable and flexible communication architectures with suitable performance. Moreover, NoC provides the SoC architects with a tool for designing on-Chip communication systems quickly, thus increasing productivity and reducing time to market. NoC is a non-centralized architecture that may be physically implemented as a distributed communication infrastructure.
A potential issue when designing NoCs is that they have to guarantee deadlock-free operations. Deadlocks that can arise in NoCs can be broadly categorized in two classes, namely the so-called routing-dependent deadlocks and the so-called message-dependent deadlocks. It is generally admitted that routing-dependent deadlocks occur when there is a cyclic dependency of resources created by the packets on the various paths in the network. Numerous routing techniques, either based on avoidance or recovery, in which restricted routing functions are provided, have been developed and today's NoC designs are mostly free from routing-dependent deadlocks. However, obtaining a message-dependent deadlock-free network operation may still be an issue.
Message-dependent-deadlocks occur when interactions and dependencies are created between different message types at network endpoints, when they share resources in the network. Even when the underlying network is designed to be free from routing-dependent deadlocks, the message-level deadlocks can block the network indefinitely, thereby affecting proper system operation. Nevertheless, some attempts have been made to avoid message-dependent deadlocks.
Message-dependent deadlocks avoidance approaches can be broadly categorized into four classes. Buffer sizing comprises providing sufficient amounts of buffers at network endpoints to be reduce congestion. This approach may not, however, be suitable to the on-chip domain for area cost reasons. End-to-end flow control may be based on the guarantee that no data is lost in the network due to buffer overflow because of a node in the network is allowed to send a packet over the network if and only if a sufficient memory space is available in a destination node of the network. This flow control process may be implemented using end-to-end credits exchange between an emitter node and a receiver node. A downside of a credit based end-to-end flow control is that at network endpoints, namely, in network interfaces of the node, each connection uses dedicated buffers, which can represent a cost in a case of multiple emitter nodes addressing data to a same receiver node.
Strict ordering comprises ordering network resources by introducing physical or virtual logically independent networks for each message type. For example, each router of the network needs two virtual channels. One channel is used for the request messages, and the other channel is used for the response messages. This separation of message types is maintained at all the nodes in the network.
In such a case, the request network is built separately from the response network. According to this approach, designing the network can become a complex process since it is not possible to know, when designing the network, the total number of virtual channels needed to route the messages through the nodes. At last, virtual circuits are an extreme case of strict ordering, in which each connection of the network between the nodes has its own logical network. Virtual circuits lead to an area penalty and to a less than optimum allocated resource utilization.